//题目:
// 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
// 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
#include<iostream>

using namespace std;
//代码
// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//代码:
class Solution {
public:
    // ListNode* swapPairs(ListNode* head) {
    //     // if(head==nullptr)return head;
    //     // ListNode* cur=head,*right=head->next,*parent;
    //     // while(right)
    //     // {
    //     //     //cur没有parent
    //     //     if(cur==head)
    //     //     {
    //     //         cur->next=right->next;
    //     //         right->next=cur;
    //     //         head=right;//标记头结点
    //     //         //判断是否还需要循环下去
    //     //         parent=cur;
    //     //         if(cur->next && cur->next->next)
    //     //             cur=cur->next,right=cur->next;
    //     //         else 
    //     //             break;
    //     //     }
    //     //     else 
    //     //     {   
    //     //         parent->next=right;
    //     //         cur->next=right->next;
    //     //         right->next=cur;
    //     //         //判断是否还需要循环下去
    //     //         parent=cur;
    //     //         if(cur->next && cur->next->next)
    //     //             cur=cur->next,right=cur->next;
    //     //         else 
    //     //             break;
    //     //     }
    //     // }
    //     // return head;
    //     if(head==nullptr || head->next==nullptr)return head;
    //     ListNode* virtual_head=new ListNode(0);
    //     virtual_head->next=head;
    //     ListNode* parent=virtual_head,*cur=head,*next=cur->next;
    //     while(next){
    //         parent->next=next;
    //         cur->next=next->next;
    //         next->next=cur;
    //         //判断是否需要继续
    //         if(cur->next && cur->next->next){
    //             parent=cur;
    //             cur=cur->next;
    //             next=cur->next;
    //         }
    //         else break;
    //     }
    //     parent=virtual_head->next;
    //     delete virtual_head;
    //     return parent;
    // }

    ListNode* cursion(ListNode* cur,ListNode* next)
    {
        if(cur==nullptr || next==nullptr)return cur;

        ListNode* node=next->next==nullptr?nullptr:cursion(next->next,next->next->next);//交换后面两个

        cur->next=node;//让左节点指向下一组的next
        next->next=cur;//让右节点指向本组的左节点

        return next;
    }
    ListNode* swapPairs(ListNode* head)
    {
        if(head==nullptr || head->next==nullptr)return head;

        return cursion(head,head->next);
    }
};